/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    return pf.open(indexname, mode);
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
IndexCursor cursor;
BTLeafNode leaf;
BTLeafNode newleaf;
BTNonLeafNode root;
PageId leafPid;
int siblingKey;
int endPid = pf.endPid();

char temp[10];

pf.read(0, temp);

memcpy(&treeHeight, temp, 4);

BTreeIndex::locatePid(key, leafPid);

leaf.read(leafPid, pf);

if (leaf.getKeyCount() == 85){
if (treeHeight > 0){
leaf.insertAndSplit(key,rid, newleaf,siblingKey);
newleaf.setNextNodePtr(leaf.getNextNodePtr());
leaf.setNextNodePtr(endPid);
leaf.write(leafPid,pf);
newleaf.write(endPid, pf);

BTreeIndex::overflow_insert(key, siblingKey, leafPid, endPid, treeHeight-1, true);

}
else{
leaf.insertAndSplit(key, rid, newleaf, siblingKey);
newleaf.setNextNodePtr(leaf.getNextNodePtr());
leaf.setNextNodePtr(endPid);

leaf.write(leafPid, pf);
newleaf.write(endPid, pf);
root.initializeRoot(leafPid, key, endPid+1);
root.write(endPid+1, pf);
treeHeight++;

pf.write(0, &treeHeight);

rootPid = endPid+1; 
}
}
else
leaf.insert(key, rid);
leaf.write(leafPid, pf);

return 0;
}

RC BTreeIndex::overflow_insert(int key, int siblingKey, PageId pid1, PageId pid2, int height, bool leafoverflow){
BTNonLeafNode nonleaf;
BTNonLeafNode newnonleaf;
BTNonLeafNode newRoot;
int midkey;
int endPid = pf.endPid();
bool overflow;

nonleaf.read(treePath[height], pf);

if (height == 0){
if (nonleaf.getKeyCount()==127){
nonleaf.insertAndSplit(siblingKey, pid2, newnonleaf, midkey);
nonleaf.write(treePath[height], pf);
newnonleaf.write(endPid, pf);

newRoot.initializeRoot(treePath[height], midkey,endPid );
newRoot.write(endPid+1,pf);
treeHeight++;
pf.write(0, &treeHeight);
}
else{
//RECORD TREE HEIGHT, ROOT NODE IN PF!!!!!!!! ETC.  
nonleaf.insert(key, pid2);
nonleaf.write(treePath[height], pf);
}
}
else{

if (nonleaf.getKeyCount() == 127){
if (leafoverflow)
nonleaf.insertAndSplit(siblingKey, pid2, newnonleaf, midkey);
else{
nonleaf.insertAndSplit(key, pid2, newnonleaf, midkey);
}
//INSERT AND SPLIT WORK?


nonleaf.write(treePath[height], pf);
newnonleaf.write(endPid, pf);

overflow = false;

return overflow_insert(midkey, siblingKey, treePath[height], endPid, height - 1, overflow); 

}
else{
if (leafoverflow)
nonleaf.insert(pid2, siblingKey);
else{
nonleaf.insert(pid2, siblingKey);
}
nonleaf.write(treePath[height], pf);
return 0;
}
}
return 0;
}



/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
int tree_height = 0;
BTNonLeafNode nonleaf;
BTLeafNode leaf;
PageId childptr;
PageId leafptr;
int eid;

char temp[10];

pf.read(0, temp);

memcpy(&treeHeight, temp, 4);

if (treeHeight == 0){
leaf.read(rootPid, pf);
leaf.locate(searchKey, eid);
cursor.pid = rootPid;
cursor.eid = eid;
}
else{

nonleaf.read(rootPid, pf);
nonleaf.locateChildPtr(searchKey, childptr);

tree_height++;
BTreeIndex::findkey(searchKey, tree_height, childptr, leafptr); 

leaf.read(leafptr, pf);
if(leaf.locate(searchKey, eid) == 0){
cursor.pid = childptr;
cursor.eid = eid;
}
else{
leafptr = leaf.getNextNodePtr();
leaf.read(leafptr, pf);
leaf.locate(searchKey, eid);
cursor.pid = childptr;
cursor.eid = eid;
}
}
return 0;
}

RC BTreeIndex::locatePid(int searchKey, PageId& pid)
{
int tree_height = 0;
BTNonLeafNode nonleaf;
BTLeafNode leaf;
PageId childptr;
PageId leafptr;
int eid;

if (treeHeight == 0){
pid = rootPid;
}
else{
BTreeIndex::findkey(searchKey, tree_height, rootPid, leafptr);
pid = leafptr;
}
return 0;
}


//recursively go down index to find leaf entry/pid
RC BTreeIndex::findkey(int searchKey, int& height, PageId childptr, PageId& leafptr){
if(height==treeHeight){
/*BTLeafNode leaf;
int eid;

leaf.read(childptr, pf);
leaf.locate(searchKey, eid);
cursor.pid = childptr;
cursor.eid = eid;*/
leafptr = childptr;
return 0;
}
else{
BTNonLeafNode nonleaf;
PageId ptr;

treePath[height] = childptr;
nonleaf.read(childptr, pf);
nonleaf.locateChildPtr(searchKey, ptr);
height++;

return findkey(searchKey, height, ptr, leafptr); 

}
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
BTLeafNode leaf;

leaf.read(cursor.pid, pf);    
leaf.readEntry(cursor.eid, key, rid);

cursor.eid++;

if (cursor.eid > leaf.getKeyCount() - 1 || leaf.readEntry(cursor.eid, key, rid)){
cursor.pid = leaf.getNextNodePtr();
cursor.eid = 0;
}

if (cursor.pid == NULL || cursor.pid > pf.endPid())
return 1;
else
return 0;
}
